package com.fw.structure.recursion;

/**
 * 回溯算法，递归走迷宫
 */
public class MazeWay {

    public static void main(String[] args) {
        /**
         * 前景提示，
         * 1。 在一个 8 行 7 列的盘子中，设定几个挡板，走出迷宫就算ok
         * 2。 定义终点，在第7行 第6列 就为终点，走到这里就代表走出成功
         * 3。 1，代表挡板， 2 ，代表 已经走过，3， 代表此路不通。
         * 4。 走迷宫策略， 下  右  上  左
         */

        //1.定义棋盘
        int mazeArr[] [] = new int[8][7];
        //2. 设定 挡板
        for (int i = 0; i < mazeArr.length; i++) {
            for (int i1 = 0; i1 < mazeArr[i].length; i1++) {
                mazeArr[0][i1] = 1;
                mazeArr[mazeArr.length - 1][i1] = 1;
            }
            mazeArr[i][0] = 1;
            mazeArr[i][mazeArr[i].length -1] = 1;
        }

        mazeArr[3][1]=1;
        mazeArr[4][1]=1;


        // 查看挡板
        for (int i = 0; i < mazeArr.length; i++) {
            for (int i1 = 0; i1 < mazeArr[i].length; i1++) {

                System.out.printf("%d\t",mazeArr[i][i1]);
            }
            System.out.println();

        }

        System.out.println();
        // 开始走迷宫
        wayMaze(mazeArr,1,1);
        // 查看挡板
        for (int i = 0; i < mazeArr.length; i++) {
            for (int i1 = 0; i1 < mazeArr[i].length; i1++) {

                System.out.printf("%d\t",mazeArr[i][i1]);
            }
            System.out.println();

        }

    }

    /**
     * 开始走迷宫
     */
    public static  boolean wayMaze(int[][] map,int i,int j) {
        // 如果到达了终点说明已然成功
        if (map[6][5] == 2) {
            return true;
        } else if (map[i][j] == 0){

            // 假定是一个可走的路线
            map[i][j] = 2;
            //下  右  上  左  -> 找路策略
            if (wayMaze(map, i + 1, j)) {
                return true;
            } else if (wayMaze(map, i, j + 1)) {
                return true;
            } else if (wayMaze(map, i - 1, j)) {
                return true;
            } else if (wayMaze(map, i, j - 1)) {
                return true;
            } else {
                // 如果都不行，说明此路不通。
                map[i][j] = 3;
                return false;
            }
        }else{
            // 如果 代码能执行到这里 说明  map[i][j] 肯定是 1，2，3
            return false;

        }


    }
}
